home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 11 Learning / 04 Mommersteeg / Predictors / StringMatchPredictor.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-09-23  |  5.3 KB  |  142 lines
  1. //----------------------------------------------------------------------------------------------
  2. // Sequential Prediction Demo: The positioning pattern
  3. // 
  4. // Author:  Fri Mommersteeg
  5. // Date:    10-09-2001
  6. // File:    StringMatchPredictor.cpp
  7. //----------------------------------------------------------------------------------------------
  8.  
  9. //----------------------------------------------------------------------------------------------
  10. // Include files
  11. //----------------------------------------------------------------------------------------------
  12.  
  13. #include "stdafx.h"
  14. #include "StringMatchPredictor.h"
  15. #include <assert.h>
  16.  
  17. //----------------------------------------------------------------------------------------------
  18. // Setup(): sets up the predictor
  19. //----------------------------------------------------------------------------------------------
  20.  
  21. void CStringMatchPredictor::Setup(int nWindowSize, int nAlphabetSize, int nMinPerformance) {
  22.     // set up window
  23.     m_nWindowSize = nWindowSize;
  24.     m_Window.SetSize(nWindowSize);
  25.  
  26.     // set up histogram
  27.     m_nAlphabetSize = nAlphabetSize;
  28.     m_Histogram.SetSize(nAlphabetSize);
  29.  
  30.     m_nMinPerformance = nMinPerformance;    
  31. }
  32.  
  33. //----------------------------------------------------------------------------------------------
  34. // GetPrediction(): determines the prediction using string-matching prediction
  35. //----------------------------------------------------------------------------------------------
  36.  
  37. bool CStringMatchPredictor::GetPrediction(int &Prediction) {
  38.     // return cached prediction value
  39.     Prediction = m_nPrediction;
  40.     return m_nMaxSize >= m_nMinPerformance;
  41. }
  42.  
  43. //----------------------------------------------------------------------------------------------
  44. // Reset(): resets the predictor
  45. //----------------------------------------------------------------------------------------------
  46.  
  47. void CStringMatchPredictor::Reset() {    
  48.     m_nMaxSize = 0; 
  49.     m_nPrediction = 0;
  50.     m_nSequenceLength = 0;
  51.  
  52.     // clear window
  53.     m_Window.SetSize(m_nWindowSize);
  54.  
  55.     // clear histogram
  56.     for (int i=0; i<m_nAlphabetSize; i++) {
  57.         m_Histogram[i].RemoveAll();
  58.     }
  59. }
  60.  
  61. //----------------------------------------------------------------------------------------------
  62. // HasNeighbour(): checks if the given window entry has the specified left-hand neighbour
  63. //----------------------------------------------------------------------------------------------
  64.  
  65. BOOL CStringMatchPredictor::HasNeighbour(int iWindowPosition, int Neighbour) {
  66.     // is element at iWindowPosition preceded by Neighbour?
  67.     if (iWindowPosition > 0) {
  68.         if (m_Window[iWindowPosition - 1].Element == Neighbour) {
  69.             return TRUE;
  70.         }
  71.     }
  72.     return FALSE;
  73. }
  74.  
  75. //----------------------------------------------------------------------------------------------
  76. // NeighbourSize(): determines the match size of the left-hand neighbour of the specified 
  77. //                    window entry (which is only valid in special situations)
  78. //----------------------------------------------------------------------------------------------
  79.  
  80. int    CStringMatchPredictor::GetNeighbourSize(int iWindowPosition) {
  81.     // calcalute the size of the substring for the lower-index neighbour    
  82.     return m_Window[iWindowPosition-1].nMatchSize;
  83. }
  84.  
  85. //----------------------------------------------------------------------------------------------
  86. // Update(): updates the predictor with the next element in the sequence
  87. //----------------------------------------------------------------------------------------------
  88.  
  89. void CStringMatchPredictor::Update(int NextElement) {
  90.  
  91.     // calculate lenghts of all substrings matching the tail
  92.     int nSize = m_Histogram[NextElement].GetSize();
  93.     int nMaxLength = 0, nMaxPosition;
  94.     int i = 0;
  95.  
  96.     // find all occurrences of NextElement in the window
  97.     while (i < nSize) {
  98.  
  99.         // retrieve the i-th occurence of NextElement
  100.         THistogramData & hd = m_Histogram[NextElement][i];
  101.         
  102.         // determine the position of this occurrence in the window
  103.         int iWindowPosition = m_Window.GetSize() - (m_nSequenceLength - hd.nSequencePosition);
  104.  
  105.         if (HasNeighbour(iWindowPosition, m_PrevElement)) {
  106.             // if this occurrence is preceded by PrevElement, we create a longer substring
  107.             m_Window[iWindowPosition].nMatchSize = GetNeighbourSize(iWindowPosition) + 1;
  108.         } else {
  109.             // else the size of this substring has to be one
  110.             m_Window[iWindowPosition].nMatchSize = 1;
  111.         }
  112.  
  113.         // keep track of the length and position of the longest substring encountered so far
  114.         if (m_Window[iWindowPosition].nMatchSize > nMaxLength) {
  115.             nMaxLength = m_Window[iWindowPosition].nMatchSize;
  116.             nMaxPosition = hd.nSequencePosition;
  117.         }
  118.         i++;
  119.     }
  120.  
  121.     // add NextElement to the histogram 
  122.     m_Histogram[NextElement].AddHead(THistogramData(m_nSequenceLength));
  123.  
  124.     // remove element dropped from the window also from histogram
  125.     TSequenceData * pDropped = m_Window.Add(TSequenceData(NextElement));
  126.     if (pDropped != NULL) {        
  127.         m_Histogram[pDropped->Element].RemoveTail();
  128.     }
  129.  
  130.     // update predictor/sequence information
  131.     m_nSequenceLength++;
  132.     m_PrevElement = NextElement;
  133.     m_nMaxSize = nMaxLength;
  134.     m_nMaxPosition = m_Window.GetSize() - (m_nSequenceLength - nMaxPosition);
  135.  
  136.     // calculate predicted successor (if a substring was found)
  137.     if (nMaxLength > 0) {
  138.         int nSuccessorPosition = m_nMaxPosition + 1;
  139.         m_nPrediction = m_Window[nSuccessorPosition].Element;
  140.     }
  141. }
  142.